English Version

一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。

(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。

编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。

网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。

示例 1:

输入: 0 输出: ["R"] 

示例 2:

输入: 2 输出: [   "_X",   "LX" ] 

示例 3:

输入: 5 输出: [   "_U",   "X_",   "XX" ] 

说明：

• K <= 100000

我们使用哈希表 $\textit{black}$ 来记录所有黑色方格的位置，哈希表 $\textit{dirs}$ 来记录蚂蚁的四个方向。我们使用变量 $x$, $y$ 来记录蚂蚁的位置，使用变量 $p$ 来记录蚂蚁的方向。我们使用变量 $x_1$, $y_1$, $x_2$, $y_2$ 来记录所有黑色方格的最小横坐标、最小纵坐标、最大横坐标、最大纵坐标。

我们模拟蚂蚁的行走过程。如果蚂蚁所在的方格是白色的，那么蚂蚁向右转 $90$ 度，将方格涂黑，向前移动一个单位。如果蚂蚁所在的方格是黑色的，那么蚂蚁向左转 $90$ 度，将方格涂白，向前移动一个单位。在模拟的过程中，我们不断更新 $x_1$, $y_1$, $x_2$, $y_2$ 的值，使得它们能够包含蚂蚁走过的所有方格。

模拟结束后，我们根据 $x_1$, $y_1$, $x_2$, $y_2$ 的值，构造出答案矩阵 $g$。然后，我们将蚂蚁所在的位置涂上蚂蚁的方向，同时将所有黑色方格涂上 $X$，最后返回答案矩阵。

时间复杂度 $O(K)$，空间复杂度 $O(K)$。其中 $K$ 是蚂蚁行走的步数。

classSolution: defprintKMoves(self, K: int) ->List[str]: x1=y1=x2=y2=0dirs= (0, 1, 0, -1, 0) d="RDLU"x=y=0p=0black=set() for_inrange(K): if (x, y) inblack: black.remove((x, y)) p= (p+3) %4else: black.add((x, y)) p= (p+1) %4x+=dirs[p] y+=dirs[p+1] x1=min(x1, x) y1=min(y1, y) x2=max(x2, x) y2=max(y2, y) m, n=x2-x1+1, y2-y1+1g= [["_"] *nfor_inrange(m)] fori, jinblack: g[i-x1][j-y1] ="X"g[x-x1][y-y1] =d[p] return ["".join(row) forrowing]

classSolution { publicList<String> printKMoves(intK) { intx1 = 0, y1 = 0, x2 = 0, y2 = 0; int[] dirs = {0, 1, 0, -1, 0}; Stringd = "RDLU"; intx = 0, y = 0, p = 0; Set<List<Integer>> black = newHashSet<>(); while (K-- > 0) { List<Integer> t = List.of(x, y); if (black.add(t)) { p = (p + 1) % 4; } else { black.remove(t); p = (p + 3) % 4; } x += dirs[p]; y += dirs[p + 1]; x1 = Math.min(x1, x); y1 = Math.min(y1, y); x2 = Math.max(x2, x); y2 = Math.max(y2, y); } intm = x2 - x1 + 1; intn = y2 - y1 + 1; char[][] g = newchar[m][n]; for (char[] row : g) { Arrays.fill(row, '_'); } for (List<Integer> t : black) { inti = t.get(0) - x1; intj = t.get(1) - y1; g[i][j] = 'X'; } g[x - x1][y - y1] = d.charAt(p); List<String> ans = newArrayList<>(); for (char[] row : g) { ans.add(String.valueOf(row)); } returnans; } }

classSolution { public: vector<string> printKMoves(int K) { int x1 = 0, y1 = 0, x2 = 0, y2 = 0; int dirs[5] = {0, 1, 0, -1, 0}; string d = "RDLU"; int x = 0, y = 0, p = 0; set<pair<int, int>> black; while (K--) { auto t = make_pair(x, y); if (black.count(t)) { black.erase(t); p = (p + 3) % 4; } else { black.insert(t); p = (p + 1) % 4; } x += dirs[p]; y += dirs[p + 1]; x1 = min(x1, x); y1 = min(y1, y); x2 = max(x2, x); y2 = max(y2, y); } int m = x2 - x1 + 1, n = y2 - y1 + 1; vector<string> g(m, string(n, '_')); for (auto& [i, j] : black) { g[i - x1][j - y1] = 'X'; } g[x - x1][y - y1] = d[p]; return g; } };

funcprintKMoves(Kint) []string { varx1, y1, x2, y2, x, y, pintdirs:= [5]int{0, 1, 0, -1, 0} d:="RDLU"typepairstruct{ x, yint } black:=map[pair]bool{} forK>0 { t:=pair{x, y} ifblack[t] { delete(black, t) p= (p+3) %4 } else { black[t] =truep= (p+1) %4 } x+=dirs[p] y+=dirs[p+1] x1=min(x1, x) y1=min(y1, y) x2=max(x2, x) y2=max(y2, y) K-- } m, n:=x2-x1+1, y2-y1+1g:=make([][]byte, m) fori:=rangeg { g[i] =make([]byte, n) forj:=rangeg[i] { g[i][j] ='_' } } fort:=rangeblack { i, j:=t.x-x1, t.y-y1g[i][j] ='X' } g[x-x1][y-y1] =d[p] ans:=make([]string, m) fori:=rangeans { ans[i] =string(g[i]) } returnans }

classSolution{func printKMoves(_ K:Int)->[String]{varx1=0,y1=0,x2=0,y2=0letdirs=[0,1,0,-1,0]letd="RDLU"varx=0,y=0,p=0varblack=Set<[Int]>()varK= K while K >0{lett=[x, y]if black.insert(t).inserted { p =(p +1)%4}else{ black.remove(t) p =(p +3)%4} x +=dirs[p] y +=dirs[p +1] x1 =min(x1, x) y1 =min(y1, y) x2 =max(x2, x) y2 =max(y2, y) K -=1}letm= x2 - x1 +1letn= y2 - y1 +1varg=Array(repeating:Array(repeating:"_", count: n), count: m)fortin black {leti=t[0]- x1 letj=t[1]- y1 g[i][j]="X"}g[x - x1][y - y1]=String(d[d.index(d.startIndex, offsetBy: p)])return g.map{ $0.joined()}}}